import java.util.ArrayList;
import java.util.List;

/**
 * 131. 分割回文串
 * https://leetcode-cn.com/problems/palindrome-partitioning/
 */
public class Solutions_131 {
    public static void main(String[] args) {
        String s = "aab";  // output: {{"a", "a", "b"}, {"aa", "b"}}
//        String s = "a";  // output: {{"a"}}

        List<List<String>> result = partition(s);
        System.out.println(result);
    }

    /**
     * 解题思路：回溯法
     */
    public static List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<>();
        if (s == null) {
            return res;
        }
        List<String> list = new ArrayList<>();
        char[] arr = s.toCharArray();
        backtrack(res, list, arr, 0);
        return res;
    }

    public static void backtrack(List<List<String>> res,
                                 List<String> list, char[] arr, int start) {
        if (start == arr.length) {
            res.add(new ArrayList<>(list));
            return;
        }
        for (int i = start; i < arr.length; i++) {
            // 判断区间 [idx, i] 是否为回文串，若是，则加入到 list 中
            boolean flag = palindrome(start, i, arr);
            if (flag) {
                String s = String.valueOf(arr, start, i - start + 1);
                list.add(s);
                backtrack(res, list, arr, i + 1);
                list.remove(list.size() - 1);
            }
        }
    }

    /**
     * 判断 [left, right] 子串是否为回文串
     * 由 left, right 左右指针向中心靠拢
     */
    public static boolean palindrome(int left, int right, char[] arr) {
        while (left < right) {
            if (arr[left] != arr[right]) {
                // [left, right] 区间子串无法形成回文串
                return false;
            }
            left ++;
            right --;
        }
        return true;
    }
}
